#include <algorithm>
#include <array>
#include <iostream>
#include <limits>
#include <vector>
// 最小路径问题 暴力搜索
int minPath(const std::vector<std::vector<int>> &path, int row, int col) {
  // 状态转移方程 d[i,j] = min(dp[i-1,j],dp[i,j-1]) + path[i,j]
  // 终止条件
  if (row == 0 && col == 0) {
    return path[0][0];
  }
  if (row < 0 || col < 0) {
    return std::numeric_limits<int>::max();
  }
  int cost =
      std::min(minPath(path, row - 1, col), minPath(path, row, col - 1)) +
      path[row][col];
  return cost;
}

// 记忆化搜索
int minPath_mem(const std::vector<std::vector<int>> &path,
                std::vector<std::vector<int>> &mem, int row, int col) {
  // 状态转移方程 d[i,j] = min(dp[i-1,j],dp[i,j-1]) + path[i,j]
  // 终止条件
  if (row == 0 && col == 0) {
    return path[0][0];
  }
  if (row < 0 || col < 0) {
    return std::numeric_limits<int>::max();
  }
  if (mem[row][col] != -1) {
    return mem[row][col];
  } else {
    int cost =
        std::min(minPath(path, row - 1, col), minPath(path, row, col - 1)) +
        path[row][col];
    mem[row][col] = cost;
    return cost;
  }
}

// 动态规划 从小到大思考问题
int minPath_dp(const std::vector<std::vector<int>> &path,
               std::vector<std::vector<int>> &dp, int n) {
  for (int row = 0; row < n; row++) {
    for (int col = 0; col < n; col++) {
      if (row == 0 && col == 0) {
        dp[row][col] = path[row][col];
        continue;
      }
      if (row == 0 && col > 0) {
        dp[row][col] = dp[row][col - 1] + path[row][col];
        continue;
      }
      if (row > 0 && col == 0) {
        dp[row][col] = dp[row - 1][col] + path[row][col];
        continue;
      }
      dp[row][col] =
          std::min(dp[row - 1][col], dp[row][col - 1]) + path[row][col];
    }
  }
  return dp[n - 1][n - 1];
}

// 空间优化
int minPath_dp_space(const std::vector<std::vector<int>> &path,
                     std::vector<std::vector<int>> &dp, int n) {
  std::vector<int> row(4, 0);
  int up = 0;
  int left = 0;
  for (int row = 0; row < n; row++) {
    for (int col = 0; col < n; col++) {
      if (row == 0 && col == 0) {
        dp[row][col] = path[row][col];
        continue;
      }
      if (row == 0 && col > 0) {
        dp[row][col] = dp[row][col - 1] + path[row][col];
        continue;
      }
      if (row > 0 && col == 0) {
        dp[row][col] = dp[row - 1][col] + path[row][col];
        continue;
      }
      dp[row][col] =
          std::min(dp[row - 1][col], dp[row][col - 1]) + path[row][col];
    }
  }
  return dp[n - 1][n - 1];
}
int main() {
  std::vector<std::vector<int>> path{
      {1, 3, 1, 5}, {2, 2, 4, 2}, {5, 3, 2, 1}, {4, 3, 5, 2}};
  // 暴力搜索
  //   int minCost = minPath(path, 3, 3);
  //   std::cout << minCost << std::endl;
  // 记忆化搜索
  //   std::vector<std::vector<int>> mem{
  //       std::vector<int>(4, -1), std::vector<int>(4, -1), std::vector<int>(4,
  //       -1), std::vector<int>(4, -1)};
  //   mem[0][0] = path[0][0];
  //   int minCost = minPath_mem(path, mem, 3, 3);
  //   std::cout << minCost << std::endl;

  std::vector<std::vector<int>> dp{
      std::vector<int>(4, 0), std::vector<int>(4, 0), std::vector<int>(4, 0),
      std::vector<int>(4, 0)};
  int minCost = minPath_dp(path, dp, 4);
  std::cout << minCost << std::endl;
  return 0;
}